package com.company.hash;

import java.util.HashSet;
import java.util.Set;

/**
 * Created by v on 16-12-7.
 */
public class QuadraticProbingHashTable<E> {
    private static final int DEFAULT_TABLE_SIZE=11;

    private HashEntry<E>[] array;
    private int currentSize;

    public QuadraticProbingHashTable(){
        this(DEFAULT_TABLE_SIZE);
    }

    public QuadraticProbingHashTable(int size){
        allocateArray(size);
        clear();
    }

    public void clear(){
        for(int i=0;i<array.length;i++){
            array[i]=null;
        }
    }

    public boolean contains(E e){
        int currentPos=findPos(e);
        if(isActive(currentPos)){
            return true;
        }
        return false;
    }

    public boolean insert(E e){
        int currentPos=findPos(e);
        if(isActive(currentPos)){
            return false;
        }

        array[currentPos]=new HashEntry<E>(e);
        if(++currentSize>array.length/2){
            rehash();
        }

        return true;
    }

    public boolean remove(E e){
        int currentPos=findPos(e);
        if(!isActive(currentPos)){
            return false;
        }
        array[currentPos].isActive=false;
        return true;
    }

    private static class HashEntry<E>{
        public E element;
        public boolean isActive;

        public HashEntry(E e){
            this(e,true);
        }

        public HashEntry(E element,boolean isActive){
            this.element =element;
            this.isActive=isActive;
        }
    }

    //判断其是否被删除,若被删除或者为空则返回false,否则返回true
    private boolean isActive(int currentPose){
        return array[currentPose]!=null&&array[currentPose].isActive;
    }

    //新建一个表
    private void allocateArray(int arraySize){
        array=new HashEntry[Prime.nextPrime(arraySize)];
    }

    //找到解决冲突后的散列值
    private int findPos(E e){
        int offset=1;
        int currentPos=myHash(e);

        while (array[currentPos]!=null
                &&!array[currentPos].element.equals(e)){
            currentPos+=offset;
            offset+=2;
            if(currentPos>=array.length){
                currentPos-=array.length;
            }
        }
        return currentPos;
    }

    //再散列
    private void rehash() {
        HashEntry<E>[] temp=array.clone();
        allocateArray(Prime.nextPrime(array.length*2));
        clear();
        for(int i=0;i<temp.length;i++){
            if(temp[i]!=null){
                insert(temp[i].element);
            }
        }
    }

    //找到散列值
    private int myHash(E e){
        int hashVal=e.hashCode();

        hashVal%=array.length;
        if(hashVal<0){
            hashVal+=array.length;
        }

        return hashVal;
    }

    public static void main(String[] args) {
        int[] randomNumber=new int[100000];
        Set<Integer> set1=new HashSet<>(101,1);
        SeparateChainingHashTable<Integer> set2=new SeparateChainingHashTable<>();
        long time1=0;
        long time2=0;

        long time;

        for(int i=0;i<randomNumber.length;i++){
            randomNumber[i]=(int)(Math.random()*randomNumber.length);
        }

        for(int k=0;k<200;k++){
            time=System.currentTimeMillis();
            for(int i=0;i<randomNumber.length;i++){
                set2.insert(randomNumber[i]);
            }
            time2+=System.currentTimeMillis()-time;

            time=System.currentTimeMillis();
            for(int i=0;i<randomNumber.length;i++){
                set1.add(randomNumber[i]);
            }
            time1+=System.currentTimeMillis()-time;

            set1.clear();
            set2.clear();
        }

        System.out.println(time1);
        System.out.println(time2);
    }
}
